#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;


//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	string A, B;
//	
//	cin >> A >> B;
//	int lena = A.size(), lenb = B.size();
//	int len = max(lena, lenb);
//	for (int i = 1; i <= lena; i++)
//		a[i] = A[lena - i] - '0';
//	for (int i = 1; i <= lena; i++)
//		b[i] = B[lena - i] - '0';
//	for (int i = 1; i <=len; i++)
//	{
//		c[i] += a[i] + b[i];
//		c[i + 1] = c[i] / 10;
//		c[i] = c[i] % 10;
//	}
//	if (c[len + 1])
//		len++;
//	for (int i = len; i >= 1; i--)
//		cout << c[i];
//	return 0;
//}
//int main() {
//	string A, B;
//	cin >> A >> B;
//	int lena = A.size(), lenb = B.size();
//	int len = max(lena, lenb);
//	for (int i = 1; i <= lena; i++)
//		a[i] = A[lena - i] - '0';
//	for (int i = 1; i <= lena; i++)
//		b[i] = B[lenb - i] - '0';
//	for (int i = 1; i <=len; i++)
//	{
//		c[i] += a[i] + b[i];
//		c[i + 1] = c[i] / 10;
//		c[i] %= 10;
//	}
//	if (c[len + 1]!=0)
//		len++;
//	for (int i = len; i >= 1; i--)
//		cout << c[i];
//}

//int main() {
//	string A, B;
//	cin >> A >> B;
//	int lena = A.size(), lenb = B.size();
//	int len = lena + lenb;
//	for (int i = 1; i <= lena; i++)
//		a[i] = A[lena - i] - '0';
//	for (int i = 1; i <= lenb; i++)
//		b[i] = B[lenb - i] - '0';
//	for (int i = 1; i <= lena; i++)
//		for (int j = 1; j <= lenb; j++)
//			c[i + j - 1] += a[i] * b[j];
//	
//	for (int i = 1; i <= len; i++)
//	{
//		c[i + 1] += c[i] / 10;
//		c[i] = c[i] % 10;
//	}
//	for (; !c[len];)
//		len--;
//	for (int i =max(1,len); i >= 1; i--)
//		cout << c[i];
//	return 0;
//}

//int main() {
//	string A, B;
//	cin >> A >> B;
//	int lena = A.size(), lenb = B.size();
//	for (int i = lena - 1; i >= 0; i--)a[lena - i] = A[i] - '0';
//	for (int i = lenb - 1; i >= 0; i--)b[lenb - i] = B[i] - '0';
//	for (int i = 1; i <= lena; i++)
//		for (int j = 1; j <= lenb; j++)
//			c[i + j - 1] += a[i] * b[j];
//	int len = lena + lenb;
//	for (int i = 1; i <= len; i++)
//	{
//		c[i + 1] += c[i] / 10;
//		c[i] %= 10;
//	}
//	for (;!c[len]; )
//	{
//		len--;
//	}
//	for (int i = max(1,len); i >=1; i--)
//	{
//		cout << c[i];
//	}
//}
//int main() {
//	string A, B;
//	cin >> A >> B;
//	int lena = A.size(), lenb = B.size();
//	int len = lena + lenb;
//	for (int i = 1; i <= lena; i++)a[i] = A[lena - i] - '0';
//	for (int i = 1; i <= lenb; i++)b[i] = B[lenb - i] - '0';
//	for (int i = 1; i <= lena; i++)
//		for (int j = 1; j <= lenb; j++)
//		{
//			c[i + j - 1] += a[i] * b[j];
//		}
//	for (int i = 1; i <= len; i++)
//	{
//		c[i + 1] += c[i] / 10;
//		c[i] %= 10;
//	}
//	for (; !c[len];)
//		len--;
//	for (int i = max(1,len); i >=1; i--)
//	{
//		cout << c[i];
//	}
//	return 0;
//}

//struct Bigint {
//	int len, a[maxn];
//	Bigint(int x = 0) {
//		memset(a, 0, sizeof(a));
//		for ( len = 1; x; len++)
//		{
//			a[len] = x % 10;
//			x = x / 10;
//		}
//		len--;
//	}
//	int &operator[](int i) {
//		return a[i];
//	}
//	void flatten(int L) {
//		len = L;
//		for (int i = 1; i <= len; i++)
//		{
//			a[i + 1] += a[i] / 10;
//			a[i] %= 10;
//		}
//		for (; !a[len];)
//			len--;
//	}
//	void print() {
//		for (int i = max(1,len); i >= 1; i--)
//		{
//			cout << a[i];;
//		}
//	}
//};
//Bigint operator+(Bigint a, Bigint b) {
//	Bigint c;
//	int len = max(a.len, b.len);
//	for (int i = 1; i <= len; i++)
//	{
//		c[i] += a[i] + b[i];
//	}
//	c.flatten(len + 1);
//	return c;
//}
//Bigint operator*(Bigint a, int b) {
//	Bigint c;
//	int len = a.len;
//	for (int i = 1; i <= len; i++)
//	{
//		c[i] = a[i] * b;
//	}
//	c.flatten(len + 11);
//	return c;
//}
//int main() {
//	Bigint ans(0), fac(1);
//	int m;
//	cin >> m;
//	for (int i = 1; i <= m; i++)
//	{
//		fac = fac * i;
//		ans = ans + fac;
//	}
//	ans.print();
//	return 0;
//}
//int a[510][510], b[510][510];
//int main() {
//	int n, m;
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <=n; j++)
//		{
//			a[i][j] = (i - 1) * n + j;
//			b[i][j] = (i - 1) * n + j;
//		}
//	while (m--) {
//		int x, y, r, z;
//		cin >> x >> y >> r >> z;
//		if (!z) {
//			for (int i = -r; i <= r; i++)
//				for (int j = -r; j <= r; j++)
//				{
//					a[x + i][y + j] = b[x - j][y + i];
//				}
//		}
//		else
//		{
//			for (int i = -r; i <= r; i++)
//				for (int j = -r; j <= r; j++)
//				{
//					a[x + i][y + j] = b[x + j][y - i];
//				}
//		}
//		for (int i = 1; i <= n; i++)
//			for (int j = 1; j <= n; j++)
//			{
//				b[i][j] = a[i][j];
//			}
//	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= n; j++)
//		{
//			cout << a[i][j] << ' ';
//		}
//		cout << '\n';
//	}
//	
//	return 0;
//}
